package com.javabasic.algorithm.leetcode;

import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

public class ImplementStackUsingQueues {
}

/**
 * 双队列实现stack
 * 原理：固定某一时刻只能有有一个作为输入元素的入栈队，类似双stack实现queue的解法
 * pop(): 如果入栈队不为空，就将入栈队的元素[除了“栈顶元素”]放入到定一个队列中，然后将栈顶元素弹出
 *        如果入栈队为空，就将不是入栈队的元素[除了“栈顶元素”]放入栈队中，然后修改入栈队
 *
 * peek(): 原理和pop()函数一样，只不过不要删除只取出“栈顶”元素
 * 
 */
class MyStack {

    Queue<Integer> queue1, queue2;
    // flag = false 表示输入栈队为queue1，flag = true 表示输入栈队为queue2
    boolean flag;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        queue1 = new LinkedBlockingQueue<>();
        queue2 = new LinkedBlockingQueue<>();
        flag = false;
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        if (!flag) {
            queue1.offer(x);
        } else {
            queue2.offer(x);
        }
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        if (!flag) {
            if (queue1.isEmpty()) {
                while (queue2.size() > 1) {
                    queue1.offer(queue2.poll());
                }
                flag = true;
                return queue2.poll();
            } else {
                while (queue1.size() > 1) {
                    queue2.offer(queue1.poll());
                }
                return queue1.poll();
            }
        } else {
            if (queue2.isEmpty()) {
                while (queue1.size() > 1) {
                    queue2.offer(queue1.poll());
                }
                flag = false;
                return queue1.poll();
            } else {
                while (queue2.size() > 1) {
                    queue1.offer(queue2.poll());
                }
                return queue2.poll();
            }
        }
    }

    /**
     * Get the top element.
     */
    public int top() {
        if (!flag) {
            if (queue1.isEmpty()) {
                while (queue2.size() > 1) {
                    queue1.offer(queue2.poll());
                }
                flag = true;
                return queue2.peek();
            } else {
                while (queue1.size() > 1) {
                    queue2.offer(queue1.poll());
                }
                return queue1.peek();
            }
        } else {
            if (queue2.isEmpty()) {
                while (queue1.size() > 1) {
                    queue2.offer(queue1.poll());
                }
                flag = false;
                return queue1.peek();
            } else {
                while (queue2.size() > 1) {
                    queue1.offer(queue2.poll());
                }
                return queue2.peek();
            }
        }
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

/**
 * 解法二：队头转栈顶
 */
class MyStack2 {

    Queue<Integer> queue1, queue2;

    /** Initialize your data structure here. */
    public MyStack2() {
        queue1 = new LinkedBlockingQueue<>();
        queue2 = new LinkedBlockingQueue<>();
    }

    /**
     * 精髓所在，将队头转栈顶
     */
    /** Push element x onto stack. */
    public void push(int x) {
        queue1.offer(x);
        while (!queue2.isEmpty()) {
            queue1.offer(queue2.poll());
        }
        Queue queue = queue1;
        queue1 = queue2;
        queue2 = queue;
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue2.poll();
    }

    /** Get the top element. */
    public int top() {
        return queue2.peek();
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue2.isEmpty();
    }
};